package text111;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution11 {
	 public List<List<Integer>> levelOrder(TreeNode root) {
     	//创建队列
			Queue<TreeNode> queue = new LinkedList();
			//创建动态数组
			List<List<Integer>> res = new ArrayList<List<Integer>>();
		//	ArrayList<Integer> res = new ArrayList<Integer>();
		//	List<Integer>list = new ArrayList<Integer>();
			//要判断根节点是否为空值		
			//根左右依次入队
			if (root==null) {
				return res;
			}
			if (root!=null) {
				queue.add(root);
				while(!queue.isEmpty()) {
					//备份
					//TreeNode tmpNode = queue.poll();
              //记录每一行的数
			    List<Integer>list = new ArrayList<Integer>();
					int size = queue.size();
					for (int i = 0; i <size; i++) {
						TreeNode tmpNode = queue.poll();
						list.add(tmpNode.val);
						if (tmpNode.left!=null) {queue.add(tmpNode.left);}
						if (tmpNode.right!=null) {queue.add(tmpNode.right);	}	
					}
                  res.add(list);
					//queue.size();
					//res.add(tmpNode.val);
				}
			}

			return res;
	    }

	/*	 
	 public List<List<Integer>> levelOrder(TreeNode root) {
	        Queue<TreeNode> queue = new LinkedList<>();
	        List<List<Integer>> res = new ArrayList<>();
	        if(root != null) queue.add(root);
	        while(!queue.isEmpty()) {
	            List<Integer> tmp = new ArrayList<>();
	            //记录每一层的数组长度，递减计算
	            
	            for(int i = queue.size(); i > 0; i--) {
	                TreeNode node = queue.poll();
	                tmp.add(node.val);
	                if(node.left != null) queue.add(node.left);
	                if(node.right != null) queue.add(node.right);
	            }
	            res.add(tmp);
	        }
	        return res;
	    }
*/
}










